package com.leetcode.partition8;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * @author `RKC`
 * @date 2021/11/29 8:55
 */
public class LC786第K个最小的素数分数 {

    public static int[] kthSmallestPrimeFraction(int[] arr, int k) {
        //因为arr单调递增，且对于任意一对i和j（i<j），其对应的arr[i]/arr[j]的范围都在(0, 1)；通过枚举(0, 1)，
        double right = 1, left = 0;
        while (true) {
            double mid = (left + right) / 2;
            //双指针检查当前的mid在数组中每对arr[i]/arr[j]排名第几，如果排名大于了k，需要移动right指针减少mid，如果排名小于了k，需要移动left指针
            int rank = 0, num1 = 0, num2 = 1;
            //i、j指针分别指向分子和分母，j每次向后移动一位，表示枚举的不同分母，i可以不断向右枚举，保证arr[i]/arr[j]<mid一定成立
            for (int i = -1, j = 1; j < arr.length; j++) {
                while (arr[i + 1] * 1.0 / arr[j] < mid) {
                    i++;
                    if (arr[i] * 1.0 / arr[j] > num1 * 1.0 / num2) {
                        num1 = arr[i];
                        num2 = arr[j];
                    }
                }
                rank += i + 1;
            }
            if (rank == k) return new int[]{num1, num2};
            if (rank > k) right = mid;
            else left = mid;
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 5};
        int k = 3;
        System.out.println(Arrays.toString(kthSmallestPrimeFraction(arr, k)));
    }

    private static int[] enumeration(int[] arr, int k) {
        Map<Float, int[]> map = new HashMap<>();
        PriorityQueue<Float> priorityQueue = new PriorityQueue<>();
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                float fraction = (float) (arr[i] * 1.0 / arr[j]);
                priorityQueue.add(fraction);
                map.put(fraction, new int[]{arr[i], arr[j]});
            }
        }
        for (int i = 1; i < k; i++) {
            priorityQueue.poll();
        }
        return map.get(priorityQueue.peek());
    }
}
